package mo.tags.backtrack.classify;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class L40 {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(res, combination, candidates, 0, target);
        return res;
    }

    private void backtrack(List<List<Integer>> res, List<Integer> combination, int[] candidates, int idx, int target) {
        if (target == 0) {
            res.add(new ArrayList<>(combination));
            return;
        }
        for (int i = idx; i < candidates.length; i++) {
            //已经找到一个解，如果后面的值与前面相等
            if (i > idx && candidates[i] == candidates[i-1]) {
                continue;
            }
            if (candidates[i] <= target) {
                combination.add(candidates[i]);
                backtrack(res, combination, candidates, i+1, target-candidates[i]);
                combination.remove(combination.size()-1);
            }
        }

    }

    public static void main(String[] args) {
        L40 test = new L40();
        System.out.println(test.combinationSum2(new int[]{2,5,2,1,2}, 5));
    }
}
